import io.netty.util.internal.StringUtil;
import io.swagger.models.auth.In;
import org.apache.commons.collections.map.LinkedMap;
import org.junit.Test;

import java.util.*;
import java.util.stream.Stream;

public class NowCode {
    /**
     * 描述
     * 给定一个数组，请你编写一个函数，返回该数组排序后的形式。
     * 示例1
     * 输入：
     * [5,2,3,1,4]
     * 返回值：
     * [1,2,3,4,5]
     * 示例2
     * 输入：
     * [5,1,6,2,5]
     * 返回值：
     * [1,2,5,5,6]
     * 复制
     * 备注：
     * 数组的长度不大于100000，数组中每个数的绝对值不超过10^9
     * @return
     */
    @Test
    public void sort1(){

        int []arr= new int[]{134883660,915476619,624665380,557642719,376286078,54228154,513042187,445691850,223390027,796264165,657270079,334570247,755678079,983324245,832852878,29647838,735802031,646828123,335459801,432937804,625636129,229957573,522228599,954450011,234588473,987202808,918558314,915043870,294103354,957981318,216324228,212041464,671921748,585176831,848373893,586455349,334166986,814892133,822395504,512093577,259749711,379961563,107031172,106025648,694414314,142511646,210763992,903412422,54735646,198884503,287535250,72975825,378617966,970837727,208112561,367046140,110120784,883633309,915343432,945413389,360251369,960155036,943654302,95418769,394793929,201456377,942104371,161235735,449997911,591314324,27378364,421697730,830340095,618060973,496133923,487132043,797157594,755790169,163869136,74744559,876608470,939530005,793407251,246919373,717250087,212391866,74295966,674216796,287879246,975357202,151160341,708272146,761482640,534210499,520103841,718312375};
        int l=0,r=arr.length-1;

//        if (arr==null||arr.length==1){
//            return arr;
//        }
        //递归版快速排序
        //dgQuickSort(arr,  l, r);
        merge_sort(arr);
    }
    /**
     * 递归版快速排序
     * @param arr 待排数组
     * @param l     数组左下标
     * @param r     数组右下标
     * @return      排完结果
     */
    private void dgQuickSort(int[] arr, int l, int r) {
    /**
     * 分析：显然使用快输排序,每次排完序能确定一个数（基数tag）的最终位置
     * 1.初始化基数tag=arr[0],当前循环中保持不变;
     * 2.
     *    arr[l]=arr[0];
     *   1).对数组从右到左遍历←，找到第一个小于tag的数arr[r],交换arr[l],l++;
     *   2).对数组从左到右遍历→，找到第一个大于tag的数arr[l],交换arr[r],r--;
     * 3.核心过程
     * 【1，5，3，2，6，7，8，0，9，4】;
     *      tag=arr[0]=1;
     * 【1，5，3，2，6，7，8，0，9，4】;
     *                                             ←
     *  arr[l]=arr[0]=1, arr[r]=arr[7]=0;
     *  swag:←→
     * 【0，5，3，2，6，7，8，1，9，4】;
     *       ↑                         ↑
     *                                   tag=1;
     *     →
     *  arr[l]=arr[1]=5, arr[r]=arr[7]=1;
     *  swag:←→
     * 【0，1，3，2，6，7，8，5，9，4】;
     *       ↑                         ↑
     *       tag=1;
     *                                   ←
     *        ← l==r, continue loop  ;
     * 【0，1，3，2，6，7，8，5，9，4】;
     *        --
     *  4.逻辑处理
     *      （1）. 递归：终止条件：l==r
     *                a:先来一遍，确定第一个数的最终位置之后，已这个数为分界限，分而治之
     *      （2）. 循环
     */
        if(l<r){
            int part=partition(arr,l,r);
            dgQuickSort(arr, l, part-1);
            dgQuickSort(arr,part+1,r);
        }
    }
    /**
     * 数据排名
     * @param arr 待排数组
     * @param l     数组左下标
     * @param r     数组右下标
     * @return      位置
     */
    private int partition(int[] arr, int l, int r) {
        int tag=arr[l];
        while (l<r){
            while (l<r&&arr[r]>=tag){//查找
                r--;
            }
            swag(arr,l,r);//交换
            while (l<r&&arr[l]<=tag){
                l++;
            }
            swag(arr, l, r);
        }
        return l;
    }

    private void swag(int[] arr, int l, int r) {
        int temp=arr[r];
        arr[r]=arr[l];
        arr[l]=temp;
    }

    /**
     * 归并排序-迭代
     * @param arr
     */
    public  void merge_sort(int [] arr){
        /**
         * 平均时间复杂度：O(nlogn)
         * 最佳时间复杂度：O(n)
         * 最差时间复杂度：O(nlogn)
         * 空间复杂度：O(n)
         * 排序方式：In-place
         * 稳定性：稳定
         * 过程分析：
         * 【1，5，3，2，6，7，8，0，9，4，4】;
         *    -----   -----   -----   -----    -----   --    第1次排序
         * 【1，5，2，3，6，7，0，8，4，9，4】;
         *    ------------    -------------   ---------    第2次排序
         * 【1，2，3，5，0，6，7，8，4，4，9】;
         *    ----------------------------   ---------    第3次排序
         * 【0，1，2，3，5，6，7，8，4，4，9】;
         *    ---------------------------------------    第4次排序
         * 【0，1，2，3，4，4，5，6，7，8，9】;
         *
         * 排序次数：n>=log2(length)
         * 逻辑：
         *  1.分割
         *  2.排序
         *  3.合并
         */
        int i = 1;
        while (i < arr.length) {
            //原理很简单，就是先两个两个合并，然后4个，然后8个……
            for (int j = 0; j + i < arr.length; j += 2 * i) {
                merge(arr, j, j + i - 1, Math.min(j + 2 * i - 1, arr.length - 1));
            }
            i = i << 1;
        }
    }
    private void merge(int[] data, int left, int center, int right) {
        int length = right - left + 1;//窗口大小
        int[] tmp = new int[length];//滑动窗口
        int tempIndex = 0;
        //_left是前半部分开始的位置，_right是后半部分开始的位置
        int _left = left;
        int _right = center + 1;
        while (_left <= center && _right <= right) {//将排序部分放入窗口
            if (data[_left] <= data[_right]) {
                tmp[tempIndex++] = data[_left++];
            } else {
                tmp[tempIndex++] = data[_right++];
            }
        }
        while (_right <= right) {
            tmp[tempIndex++] = data[_right++];
        }
        while (_left <= center) {
            tmp[tempIndex++] = data[_left++];
        }
        tempIndex = 0;
        while (tempIndex < length) {//整合窗口数据
            data[left + tempIndex] = tmp[tempIndex++];
        }
    }

    /**
     * NC78 反转链表
     * 描述
     * 输入一个链表，反转链表后，输出新链表的表头。
     * 示例1
     * 输入：
     * {1,2,3}
     * 返回值：
     * {3,2,1}
     */
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    @Test
    public void LinkedTable() {
        ListNode head=new ListNode(-1),q=head;
        int []arr=new int[]{1,3,2,4,5};
        for (int i : arr) {//创建链表
            ListNode node=new ListNode(i);
            q.next=node;
            q=node;
        }
        ReverseList(head);
    }
    public ListNode ReverseList(ListNode head){
        ListNode p=head.next,t=new ListNode(-1);
        while (p!=null){//头插法
            ListNode node=new ListNode(p.val);
            node.next=t.next;
            t.next=node;
            p=p.next;
        }
        return t;
    }

    /**
     * NC93 设计LRU缓存结构
     *描述
     * 设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
     * 1. set(key, value)：将记录(key, value)插入该结构
     * 2. get(key)：返回key对应的value值
     *
     * 提示:
     * 1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
     * 2.当缓存的大小超过K时，移除最不经常使用的记录。
     * 3.输入一个二维数组与K，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
     *    若opt=1，接下来两个整数key, value，表示set(key, value)
     *    若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
     *    对于每个opt=2，输出一个答案
     * 4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
     *
     * 进阶:你是否可以在O(1)的时间复杂度完成set和get操作
     * 示例1
     * 输入：
     *    [
     *          [1,1,1],
     *          [1,2,2],
     *          [1,3,2],
     *          [2,1],
     *          [1,4,4],
     *          [2,2]
     *   ],3
     *
     * 返回值：
     *      [1,-1]
     * 说明：
     *******************************
     *      {"1"=1,"2"=2,"3"=2}   *
     *         ↑             ↑      *
     * 最不经常使用      ↑      *
     *      最近         经常使用 *
     *                       最远     *
     ******************************
     *      [1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
     *      [1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
     *      [1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
     *      [2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
     *      [1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
     *      [2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
     * 示例2
     * 输入：
     *    [
     *          [1,1,1],
     *          [1,2,2],
     *          [2,1],
     *          [1,3,3],
     *          [2,2],
     *          [1,4,4],
     *          [2,1],
     *          [2,3],
     *          [2,4]
     *    ],2
     * 返回值：
     *      [1,-1,-1,3,4]
     * 备注：
     *      1≤K≤N≤10^5
     *  -2×10^9≤x,y≤2×10^9
     */
    @Test
    public void LRUTest(){
        int [][]arr=new int[][]{
                {1,1,1},
                {1,2,2},
                {2,1},
                {1,3,3},
                {2,2},
                {1,4,4},
                {2,1},
                {2,3},
                {2,4}
        };
        LRU(arr,3);
    }

    static class Node{//双向链表
        int key , value;
        Node prev,next;
        public Node(int key , int value){
            this.key = key;
            this.value = value;
        }
    }
    private Map<Integer,Node> map = new HashMap<>();//存储节点
    //双向链表存储节点顺序
    private Node head = new Node(-1,-1);
    private Node tail = new Node(-1,-1);
    private int k;

    public int[] LRU (int[][] operators, int k) {
        // write code here
        /**
         * LRU(最近最少使用)分析
         * 算法过程：
         *  假设页面大小为5；
         *  序列：
         *******************************
         *      {"1"=1,"2"=2,"3"=2}    *
         *         ↑             ↑       *
         * 最不经常使用      ↑       *
         *      最近         经常使用  *
         *                       最远      *
         *******************************
         */
        this.k = k;
        head.next = tail;
        tail.prev = head;
        int len =(int) Arrays.stream(operators).filter(x->x[0] == 2).count();//动态初始化数组
        int[] ans = new int[len];
        int cnt = 0;
        for(int i=0;i < operators.length ;i++){
            if(operators[i][0] == 1){
                set(operators[i][1],operators[i][2]);
            }else{
                ans[cnt++] = get(operators[i][1]);
            }
        }
        return ans;
    }
    public void set(int key,int value){//位置顺序用链表存储，和map无关
        if(get(key) > -1){//更新已有节点
            map.get(key).value = value;
        }else{
            if(map.size() == k ){//页面已存满
                int rk = tail.prev.key;
                tail.prev.prev.next = tail;
                tail.prev = tail.prev.prev;
                map.remove(rk);//删除最近最久未使用的节点
            }
            //新增节点
            Node node = new Node(key,value);
            map.put(key,node);
            removeToHead(node);
        }
    }
    public int get(int key){//位置顺序用链表存储，和map无关
        if(map.containsKey(key)){//map中有此节点
            //变更链表顺序
            Node node = map.get(key);
            node.prev.next = node.next;
            node.next.prev = node.prev;

            removeToHead(node);
            return node.value;
        }
        return -1;
    }
    public void removeToHead(Node node){
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    /**
     * NC45 实现二叉树先序，中序和后序遍历
     * 描述
     * 分别按照二叉树先序，中序和后序打印所有的节点。
     * 示例1
     * 输入：
     *   {1,2,3}
     * 返回值：
     *  [[1,2,3],[2,1,3],[2,3,1]]
     * 备注：
     *  n≤10^6
     */
    public class TreeNode{
        int val=0;
        TreeNode left=null;
        TreeNode right=null;
        TreeNode(int val){
            this.val=val;
        }
    }
    private Queue<Integer> queue = new LinkedList<>();
    @Test
    public void treeTest(){
        int []array={1,2,3};
        TreeNode root=null;
        root=preCreateTree(array,0);
        threeOrders (root);

    }
    public int[][] threeOrders (TreeNode root) {
        // write code here

        preOrder(root);
        int [][] arr=new int[3][queue.size()];
        int i=0;
        while (queue.size()>0){
            arr[0][i++]=  queue.poll();
        }
        inOrder(root);
        i=0;
        while (queue.size()>0){
            arr[1][i++]= queue.poll();
        }
        postOrder(root);
        i=0;
        while (queue.size()>0){
            arr[2][i++]= queue.poll();
        }
        return arr;
    }
    //先序遍历建树
    TreeNode preCreateTree(int []arr,int i){
        if(i>=arr.length){
            return null;
        }
        //先序建树
        TreeNode node= new TreeNode(arr[i]);
        node.left=preCreateTree(arr,2*i+1);
        node.right=preCreateTree(arr,2*i+2);
        return node;
    }
    //先序遍历
    void preOrder(TreeNode root){
        if(root==null){
            return ;
        }
        queue.add( root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    void inOrder(TreeNode root) {
        if(root==null){
            return ;
        }
        inOrder(root.left);
        queue.add( root.val);
        inOrder(root.right);
    }
    //后序遍历
    void postOrder(TreeNode root) {
        if(root==null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        queue.add( root.val);
    }

    /**
     * NC119 最小的K个数
     * 描述
     * 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
     * 0 <= k <= input.length <= 10000
     * 0 <= input[i] <= 10000
     * 示例1
     *  输入：
     *      [4,5,1,6,2,7,3,8],4
     *  返回值：
     *      [1,2,3,4]
     * 说明：
     * 返回最小的4个数即可，返回[1,3,2,4]也可以
     * 示例2
     *  输入：
     *      [1],0
     *  返回值：
     *      []
     * 示例3
     *  输入：
     *      [0,1,2,1,2],3
     *  返回值：
     *      [0,1,1]
     */
    @Test
    public void topKTest() {
        int []input=new int[]{1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
       // input=new int[]{1,3,5,2,2};
        int k=4,
                K=24,n=49;
               //K=3,n=5;
        //ArrayList<Integer> list = adjustMinHead(input, k);
        getTopK(input,n,K,0,n-1);
        final int i = input[n - K];
    }

    private ArrayList<Integer> adjustMinHead(int[] input, int k) {
        /**
         * a[]={   8  ,   3   ,   1   ,   2   ,   4   ,   5   ,   7   }
         *        a[0]  a[1]   a[2]   a[3]   a[4]   a[5]   a[6]
         * 过程分析：
         * 第一次：
         *                              a[0]                                                                   0,...,7             k=0
         *                            /      \
         *                       a[1]        a[2]                             a[i]                          len=a.length ,   root_i=(len+k)/2 - 1
         *                     /     \       /     \            ==>          /     \
         *                a[3]    a[4]   a[5]   a[6]            a[2*i+1]   a[2*i+2]                 left_i=2*i+1-k  ,   right_i=2*i+2 -k ,left_i,right_i<a.length
         *
         * 第二次：
         *                       a[0],a[1]                                                                   1,...,7             k=1
         *                            /      \
         *                       a[2]        a[3]
         *                     /     \       /
         *                a[4]    a[5]   a[6]
         *
         * 第三次：
         *                a[0],a[1],a[2]                                                                   2,...,7             k=2
         *                            /      \
         *                       a[3]        a[4]
         *                     /     \
         *                a[5]    a[6]
         *
         * 第四次：
         *         a[0],a[1],a[2],a[3]                                                                   3,...,7             k=3
         *                            /      \
         *                       a[4]        a[5]
         *                     /
         *                a[6]
         */
        int len=input.length,i=0;
        ArrayList<Integer> list=new ArrayList<>();
        while (i<k){
            for(int root_i=(len+i)/2-1;root_i>=i;root_i--){
                int     left_i=2*root_i+1-i,
                       right_i=2*root_i+2-i;//數組偏移下標計算
                builtMinHead(input,root_i,left_i,right_i);
            }
            list.add(input[i++]);
        }
        return list;
    }

    private void builtMinHead(int[] input, int root_i,int left_i,int right_i) {

        if(right_i<input.length&&input[right_i]<input[left_i]){//控制最後一個叶子节点边界
            swag(input,left_i,right_i);
        }
        if(input[left_i]<input[root_i]){
            swag(input,left_i,root_i);
        }
    }

    /**
     * NC15 求二叉树的层序遍历
     * @return
     */
    @Test
    public void levelOrder () {
        // write code here
        //1.节点遍历，放入队列
        //2.从队列中取出节点，loop
        int []input=new int[]{4,5,1,6,2,7,3,8};
        TreeNode root=preCreateTree(input,0);
        Queue<TreeNode> node=new LinkedList<>();
        ArrayList<Integer> list1=new ArrayList<>();
        ArrayList<ArrayList<Integer>> list2=new ArrayList<>();
        int level=1,//各层节点数量
                count=0;//统计各层节点数量
       if(root==null)
           return;
        node.add(root);
        while (node.size()>0){
            TreeNode q=node.poll();
            list1.add(q.val);
            //放入队列，统计节点数量
            if(q.left!=null){
                node.add(q.left);
                count++;
            }
            if(q.right!=null){
                node.add(q.right);
                count++;
            }
            //初始化与结果处理
            if(level--==1){
                level=count;
                count=0;
                list2.add(list1);
                list1=new ArrayList<>();//更新数组地址
            }
        }
    }

    /**
     * NC88 寻找第K大
     * 描述
     * 有一个整数数组，请你根据快速排序的思路，找出数组中第 大的数。
     *
     * 给定一个整数数组 ,同时给定它的大小n和要找的 ，请返回第 大的数(包括重复的元素，不用去重)，保证答案存在。
     * 要求时间复杂度
     * 示例1
     * 输入：
     *      [1,3,5,2,2],5,3
     * 返回值：
     *      2
     * 示例2
     * 输入：
     *      [10,10,9,9,8,7,5,6,4,3,4,2],12,3
     * 返回值：
     *      9
     * 说明：
     *      去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
     * @param a
     * @param n
     * @param K
     * @param left
     * @param right
     */
    public void getTopK(int[] a, int n, int K,int left,int right){
        if(left<right) {//控制边界
            int pos=position(a,left,right);
            if(pos==n-K)//只排TopK
                return ;
            else if(pos>n-K){//只排左边
                getTopK(a, n, K, left, pos - 1);
            }else{//只排右边
                getTopK(a,n,K,pos+1,right);
            }
        }
    }
    public int position(int[] a,int left,int right){
        int mid=a[left];
        while(left<right){
            while(left<right&&mid<=a[right]) {//先排右边
                right--;
            }
            swags(a,left,right);
            while(left<right&&a[left]<=mid) {//再排左边
                left++;
            }
            swags(a,left,right);
        }
        return left;
    }
    public void swags(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    /**
     * NC61 两数之和
     * 描述
     *      给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
     *      你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
     *      假设给出的数组中只存在唯一解
     * 例如：
     *      给出的数组为 {20, 70, 110, 150},目标值为90
     *      输出 index1=1, index2=2
     *
     *
     * 示例1
     * 输入：
     *      [3,2,4],6
     * 返回值：
     *      [2,3]
     * 说明：
     *      因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以输出[2,3]
     */
    @Test
    public void twoSumTest(){
        int[] numbers=new int[]{-3,4,3,90};
        int target=0;
        int[] result=twoSum( numbers,target);
    }

    /**
     * 非暴力破解法，时间复杂度O(n),空间复杂度O(n)
     * @param numbers
     * @param target
     * @return
     */
    private int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int[] result=new int[2];
        for (int i=0;i<numbers.length;i++){
            if(map.get(numbers[i])==null){//map中没有
                map.put(target-numbers[i],i+1);
            }else {
                result[0]=map.get(numbers[i]);
                result[1]=i+1;
            }
        }
         return result;
    }

    /**
     * NC33 合并两个排序的链表
     * 描述
     * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
     * 示例1
     * 输入：
     * {1,3,5},{2,4,6}
     * 返回值：
     * {1,2,3,4,5,6}
     */
    @Test
    public void linkMergeTest(){
        ListNode list1=new ListNode(-1),list2=new ListNode(-1),q=list1,p=list2;
        int[] arr1=new int[]{1,3,5},arr2=new int[]{2,4,6};
        for (int i : arr1) {
            q.next=new ListNode(i);
            q=q.next;
        }
        for (int i : arr2) {
            p.next=new ListNode(i);
            p=p.next;
        }
        ListNode node=Merge(list1.next,list2.next);
    }
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head=new ListNode(-1),
                q=head;//记录位置节点
        head.next=list1;
        while(list1!=null&&list2!=null){
            //1.比较两个链表
            while(list1!=null&&list2!=null&&list1.val<list2.val){//查找有序断，,while减少断链次数
                q=list1;//记录上一个节点
                list1=list1.next;
            }
            q.next=list2;//指向到list2
            while(list1!=null&&list2!=null&&list2.val<=list1.val){//查找有序断
                q=list2;//记录上一个节点
                list2=list2.next;
            }
            q.next=list1;//指向到list1
        }
        q.next=list1==null?list2:list1;//合并剩余节点
        return head.next;
    }

    /**
     * NC76 用两个栈实现队列
     * 描述
     * 用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
     *
     * 示例:
     * 输入:
     * ["PSH1","PSH2","POP","POP"]
     * 返回:
     * 1,2
     * 解析:
     * "PSH1":代表将1插入队列尾部
     * "PSH2":代表将2插入队列尾部
     * "POP“:代表删除一个元素，先进先出=>返回1
     * "POP“:代表删除一个元素，先进先出=>返回2
     */
    public class myQueue{
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();

        public void push(int node) {
            stack1.add(node);
        }

        public int pop() {
            //stack2为空，stack1未满，入stack2
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.add(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

    /**
     * NC68 跳台阶
     *
     * 描述
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
     * 示例1
     * 输入：
     * 2
     * 返回值：
     * 2
     * 示例2
     * 输入：
     * 7
     * 返回值：
     * 21
     * @param target
     * @return
     */
    public int jumpFloor(int target) {
        //target:1  2  3  4  5  ...
        //result:1  2  3  5  8  ...
        //target=1,result=1
        //target=2,result=2
        //target(n)=target(n-1)+target(n-2)
        int a=1,b=1;
        for(int i=1;i<target;i++){
            a=a+b;//target(n)
            b=a-b;//target(n-1)
        }
        return a;
    }

    /**
     * NC50 链表中的节点每k个一组翻转
     *描述
     * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
     * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
     * 你不能更改节点中的值，只能更改节点本身。
     * 要求空间复杂度 O(1)
     * 例如：
     * 给定的链表是1→2→3→4→5
     * 对于  k=2, 你应该返回 2→1→4→3→5
     * 对于  k=3, 你应该返回 3→2→1→4→5
     * 示例1
     * 输入：
     * {1,2,3,4,5},2
     * 返回值：
     * {2,1,4,3,5}
     */
    @Test
    public void reverseKGroupTest(){
        ListNode list=new ListNode(0),p=list;
        int[] arr1=new int[]{1};
        for (int i : arr1) {
            p.next=new ListNode(i);
            p=p.next;
        }
        ListNode listNode= reverseKGroup(list.next,1);
    }
    public ListNode reverseKGroup (ListNode head, int k) {//没有头节点
        // write code here
        ListNode res=new ListNode(0),cur=new ListNode(0),q=head,p=null,l=null;
        res.next=head;
        ListNode _head=res,pre=res;
        if(head==null){
            return head;
        }
        int i=1;
        while(q!=null){
            if(i==1){//记录待反转断链第一个节点位置
                pre=q;
            }
            q=q.next;//后移一位，防止节点序列被影响
            if(i==k){
                l=pre;//记录节点位置，用于合并其他节点
                while (i>0){//反转断链，头插法倒序
                    //截取
                    p=pre;
                    pre=pre.next;
                    //头插
                    p.next=cur.next;
                    cur.next=p;
                    i--;
                }
                //插入结果链表
                _head.next=cur.next;
                //头节点后移
                _head=l;
            }
            i++;
        }
        if(i-1!=k){//合并剩余序列
            _head.next=pre;
        }
        return res.next;
    }

    /**
     * NC41 最长无重复子数组
     * 描述
     * 给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
     * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
     * 示例1
     * 输入：
     * [2,3,4,5]
     * 返回值：
     * 4
     * 说明：
     * [2,3,4,5]是最长子数组
     * 示例2
     * 输入：
     * [2,2,3,4,3]
     * 返回值：
     * 3
     * 说明：
     * [2,3,4]是最长子数组
     */
    @Test
    public void maxLengthTest(){
        int[] arr=new int[]{1,1,3,5,7,9,7};
        arr=new int[]{2,3,4,5};
        arr=new int[]{3,3,2,1,3,3,3,1};
        final int i = maxLength(arr);
    }
    public int maxLength (int[] arr) {
        // write code here
        /**
         *          {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *      -1       0       1       2        3       4       5       6       7      arr.length
         *      left  ,windows={}
         *
         *      {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *           []
         *      1.right = 0,left=-1,res=1,windows=[3=0]
         *
         *      {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *                   []
         *      2.right = 1,left=0,res=1,windows=[3=1]
         *
         *      {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *                   [         ]
         *      3.right = 2,left=0,res=2,windows=[3=1,2=2]
         *
         *      {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *                   [                 ]
         *      4.right = 3,left=0,res=3,windows=[3=1,2=2,1=1]
         *            {    3   ,   3   ,   2   ,   1   ,   3   ,   3   ,   3   ,   1   }
         *                          [                          ]
         *      5.right = 4,left=4,res=3,windows=[3=4,2=2,1=1]
         */
        if(arr.length<2){
            return arr.length;
        }
        int left=-1;//非重复序列（滑动窗口）起始位置
        int res=0;//窗口大小
        HashMap<Integer,Integer> window=new HashMap<>();//滑动窗口存储序列
        for(int right=0;right<arr.length;right++){
            if(window.containsKey(arr[right])){//更新窗口起始位置
                left=Math.max(left,window.get(arr[right]));//window.get(arr[right])重要，被重复节点的位置
            }
            res=Math.max(res,right-left);//更新窗口大小（单调)
            window.put(arr[right],right);
        }
        return res;
    }

    /**
     * NC4 判断链表中是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        //删除法
        //如果head为空，或者他的next指向为空，直接返回false
        if (head == null || head.next == null)
            return false;
        //如果出现head.next = head表示有环
        if (head.next == head)
            return true;
        ListNode nextNode = head.next;
        //当前节点的next指向他自己，相当于把它删除了
        head.next = head;
        //然后递归，查看下一个节点
        return hasCycle(nextNode);
    }

    /**
     * NC22 合并两个有序的数组
     *
     * 描述
     * 给出一个整数数组 和有序的整数数组 ，请将数组 合并到数组 中，变成一个有序的升序数组
     * 注意：
     * 1.可以假设 数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 和 ，的数组空间大小为 +
     * 2.不要返回合并的数组，返回是空的，将数组 的数据合并到里面就好了
     * 3.数组在[0,m-1]的范围也是有序的
     *
     * 例1:
     * A: [4,5,6,0,0,0]，m=3
     * B: [1,2,3]，n=3
     * 合并过后A为:
     * A: [1,2,3,4,5,6]
     */
    @Test
    public void mergeSortArray(){
        int[] A=new int[]{4,5,6,0,0,0};
                //A=new int[]{2,5,6};
        int[] B=new int[]{1,2,3};
        int m=3,n=3;
        merge(A,m,B,n);
    }

    public void merge(int A[], int m, int B[], int n) {
        //找最大值序列，从后往前合并
        int len=m+n-1;//未排序列边 界
        m--;
        n--;
        while(n>=0&&m>=0){
            if(A[m]>B[n]){//A中大值后移
                A[len--]=A[m--];
            }else if(A[m]<B[n]){//B中大值，赋值到A的后面
                A[len--]=B[n--];
            }else { //A=B,，赋值到A的后面
                A[len--]=B[n--];
            }
        }
        while (m==-1&&n>=0){//A先排完，处理B未排部分
            A[len--]=B[n--];
        }
    }

    /**
     * NC3 链表中环的入口结点
     *给一个长度为  链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
     *
     * 数据范围：
     * 要求：空间复杂度 ，时间复杂度
     * 输入描述：
     * 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表
     * 返回值描述：
     * 返回链表的环的入口结点即可。而我们后台程序会打印这个节点
     * 示例1
     * 输入：
     * {1,2},{3,4,5}
     * 返回值：
     * 3
     * 说明：
     * 返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3
     * 示例2
     * 输入：
     * {1},{}
     * 返回值：
     * "null"
     * 说明：
     * 没有环，返回null，后台打印"null"
     * 示例3
     * 输入：
     * {},{2}
     * 复制
     * 返回值：
     * 2
     * 说明：
     * 只有环形链表节点2，返回节点2，后台打印2
     *
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null){
            return null;
        }
        ListNode slow=pHead,fast=pHead,q=pHead;
        int step=0,count=0;
        while(fast!=null&&fast.next!=null){//找到循环中的某个节点，并记录步数
            slow=slow.next;
            step++;
            fast=fast.next.next;
            if(slow==fast){
                break;
            }
        }
        if(fast==null||fast.next==null){//不是环，返回null
            return null;
        }
        while(true){
            if(q==slow&&count<step){//节点相同，起始位置步长小于环内节点步长，即找到
                return q;
            }else if(q!=slow){//节点不相同，移动起始节点和步长
                q=q.next;
                count++;
            }else{//节点相同，步长相同，移动环内节点，初始化起始节点及步长
                q=pHead;
                count=0;
                slow=slow.next;
            }
        }
    }

    /**
     * NC52 括号序列
     * 描述
     * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
     * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
     * 示例1
     * 输入：
     * "["
     * 返回值：
     * false
     * 示例2
     * 输入：
     * "[]"
     * 返回值：
     * true
     */
    @Test
    public void isValidTest(){
        final boolean valid = isValid("()");
    }
    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack=new Stack<>();
        if(s==null||s.length()==0){
            return false;
        }
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if ('{'==aChar||'['==aChar||'('==aChar) {
                stack.push(aChar);
            }else if(stack.size()>0){
                char c= stack.peek();
                switch (aChar){
                    case ')':
                        if(c=='('){
                            stack.pop();
                        }
                        break;
                    case '}':
                        if(c=='{'){
                            stack.pop();
                        }
                        break;
                    case ']':
                        if(c=='['){
                            stack.pop();
                        }
                        break;
                }
            }else {
                stack.push(aChar);
            }
        }
        return stack.size()>0?false:true;
    }

    /**
     * NC53 删除链表的倒数第n个节点
     * 描述
     * 给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针
     * 例如，
     * 给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2.
     * 删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5.
     *
     * 备注：
     * 题目保证 nn 一定是有效的
     * 请给出时间复杂度为\ O(n) O(n) 的算法
     */
    @Test
    public void removeNthFromEndTest(){
        ListNode list=new ListNode(0),p=list;
        int[] arr1=new int[]{1};
        for (int i : arr1) {
            p.next=new ListNode(i);
            p=p.next;
        }
        ListNode listNode= removeNthFromEnd(list.next,1);
    }
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head==null)
            return null;
        ListNode p=head,q=new ListNode(0);
        q.next=head;//整一个头节点
        head=q;
        while(p!=null){
            if(n==0){//p先走n步，q再走
                q=q.next;
            }else{
                n--;
            }
            p=p.next;
        }
        p=q.next;//临时存储
        q.next=p.next;//删除节点
        return head.next;
    }


    /**
     * NC1 大数加法
     * 描述
     * 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
     * （字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成）
     * 示例1
     * 输入：
     * "1","99"
     * 返回值：
     * "100"
     * 说明：
     * 1+99=100
     */
    @Test
    public void bigNumberAdd(){
        String result = solve("0", "0");
    }
    public String solve (String s, String t) {
        // write code here
        /**
         * 3242355-->Array1={3,2,4,2,3,5,5}
         * 879789-->Array2={8,7,9,7,8,9}
         *          {    3   ,   2   ,   4   ,   2   ,   3   ,   5   ,   5   }
         *
         * index:     0       1       2        3       4       5       6
         *
         *                  {    8   ,   7   ,   9   ,   7   ,   8   ,   9   }
         *
         * index:              0       1       2       3       4       5
         *                               万      千     百      十      个
         *
         *
         */
        if(s.isEmpty()&&t.isEmpty()){
            return null;
        }else if(s.isEmpty()){
            return t;
        }else if(t.isEmpty()){
            return s;
        }
        char[] val1 = s.toCharArray(),val2 = t.toCharArray();
        int len1=val1.length,len2=val2.length;
        String result="";
        if(len1>=len2){
            result=bigNumAdd(val1,val2,len1-1,len2-1);
        }else {
            result=bigNumAdd(val2,val1,len2-1,len1-1);
        }
        return result;
    }

    private String bigNumAdd(char[] val1, char[] val2, int len1, int len2) {
        int tag=0,i=0;
        StringBuilder stringBuilder = new StringBuilder();
        while (len2>=0){//同为相加
            i = val1[len1] -'0'+  val2[len2]-'0'+tag;
            tag=i/10;
            stringBuilder.insert(0,i%10);
            len2--;
            len1--;
        }
        while(len1>=0){//余位处理
            i = val1[len1] -'0'+tag;
            tag=i/10;
            stringBuilder.insert(0,i%10);
            len1--;
        }
        if(tag==1){//高位进位，补1
            stringBuilder.insert(0,tag);
        }
        return stringBuilder.toString();
    }
}
